package 美团;

import 树.TreeNode;

public class _572_另一个树的子树 {
    // 方法一：将两个树的遍历结果用字符串存储，使用str1.contains(str2)来做判断
    public boolean isSubtree(TreeNode s, TreeNode t) {
        String tree1 = postSerializable(s);
        String tree2 = postSerializable(t);

        return tree1.contains(tree2);
    }

    private String postSerializable(TreeNode t) {
        StringBuilder sb = new StringBuilder();
        postSerializable(t,sb);
        return sb.toString();
    }

    private void postSerializable(TreeNode t, StringBuilder sb) {
        if (t == null) {
            sb.append("#");
            return;
        }
        postSerializable(t.left,sb);
        postSerializable(t.right,sb);
        sb.append(t.val).append("!");
    }

    // 方法二：递归判断
    public boolean isSubtree2(TreeNode s, TreeNode t) {
       if (t == null) return true;
       if (s == null) return false;
       return isSubtree(s.left, t) || isSubtree(s.right, t) || isSameTree(s, t);
    }

    private boolean isSameTree(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        if (s.val != t.val) {
            return false;
        } else {
            return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
        }
    }
}
